package leecode;

public class LeetCode31 {
    public int countDigitOne(int n) {
        int count=0;
        for (int i = 1; i <=n ; i++) {
            int k=i;
            while (k!=0) {
                if(k%10==1){
                    count++;
                }
                k/=10;
            }
        }
        return count;
    }
    public int cuttingRope(int n) {
        if(n<=3){
            return n-1;
        }
        if(n==4){
            return 4;
        }
        long max=1;
        while(n>4){
            max*=3;
            max%=1000000007;
            n-=3;
        }
        return (int)(max*n%1000000007);
    }

    public int findNthDigit(int n) {
        int digit=1;//位数
        int count=9;//有多少这个位数的东西
        int start=1;//这个位开始的值
        while (n>count){
            n-=count;
            start*=10;
            digit+=1;
            count=digit*9*start;
        }
        int num=start+(n-1)/digit;//找到对应的那个数
        return String.valueOf(num).charAt((n-1)%digit)-'0';//找到那个对应的位数
    }
    public static int findNthDigit1(int n) {
        int digit = 1;   // n所在数字的位数
        long start = 1;  // 数字范围开始的第一个数
        long count = 9;  // 占多少位
        while(n > count){
            n -= count;
            digit++;
            start *= 10;
            count = digit * start * 9;
        }
        long num = start + (n - 1) / digit;
        return Long.toString(num).charAt((n - 1) % digit) - '0';
    }

    public static void main(String[] args) {
        findNthDigit1(11);
    }
}
